1. Field of the Invention
This invention relates to communication of information across a data network. More particularly, this invention relates to improvements in message stream synchronization in a group communication service.
2. Description of the Related Art
TABLE 1Acronyms and AbbreviationsGCSGroup Communication SystemPGMPragmatic General MulticastQoSQuality of Service
A group communication service provides multi-point to multi-point communication by organizing processes in groups. A group is a set of communication entities, which includes processes executed by servers or computers that are members of the group.
Distributed group communication systems (GCSs) enable applications to exchange messages within groups of processes in a cluster of computers. A group communication system provides a variety of semantic guarantees for the messages being exchanged, such as reliability, synchronization, and ordering. For example, in response to an application request, a group communication system may ensure that if a message addressed to the entire group is delivered to one of the group members, the message will also be delivered to all other live and connected members of the group, so that group members can act upon received messages and remain consistent with one another.
Chockler et al. provide a useful overview of group communication systems in “Group Communication Specifications: A Comprehensive Study,” ACM Computing Surveys 33:4 (December, 2001), pages 1-43, which is herein incorporated by reference. This paper focuses on view-oriented group communication systems, which provide membership and reliable multicast services to the member processes in a group. The task of a membership service is to maintain a list of the currently active and connected processes in the group. The output of the membership service is called a “view.” The reliable multicast services deliver messages to the current view members.
Various methods are known in the art for maintaining the desired message delivery order in a group communication system. Chiu et al. describe one such ordering protocol, for example, in “Total Ordering Group Communication Protocol Based on Coordinating Sequencers for Multiple Overlapping Groups,” Journal of Parallel and Distributed Computing 65 (2005), pages 437-447, which is herein incorporated by reference. Total order delivery, as described in this paper, is characterized by requiring that messages be delivered in the same relative order to each process. The protocol proposed by the authors is sequencer-based, i.e.; sequencer sites are chosen to be responsible for ordering all multicast messages in order to achieve total order delivery.
A reliable multicast protocol is often used to send and receive messages in group communication systems. Reliable multicast protocols use message or packet streams to deliver messages. An example of such a protocol is Pragmatic General Multicast (PGM), the specification of which is presented in Network Working Group RFC 3208. Each stream is globally unique and is the basic entity over which reliability is maintained. PGM supports any number of sources within a multicast group, each fully identified by a globally unique transport session identifier.
The PGM protocol proposes a ‘late-join’ option that may help to synchronize several receivers in order that they all start processing packets of a new stream from the same packet. Late joining allows a source to indicate what packets or messages receivers may request from the source's history buffer when they first receive a stream.
Another reliable multicast transport arrangement is disclosed in commonly assigned U.S. Pat. No. 6,507,586, whose disclosure is herein incorporated by reference. A data transmission system is described, which has a single transmitter and a plurality of receivers where the transmitter sends a group of data items to a subset of receivers over a one-way channel.
Another approach to message ordering is proposed in U.S. Pat. No. 6,959,323, issued to Tzeng, et al. This document describes a protocol for synchronizing states of nodes in a distributed multicasting environment. The arrangement employs a dedicated sequencer, which is responsible solely for assigning sequence numbers to multicast messages. The sequencer does not multicast the messages. Commit servers store the ordering information for each message. Data servers store the data messages sent to the group. Messages are consolidated using checkpoint servers, and sent to clients. The arrangement purports to ensure both atomicity and total order among messages sent to a multicast group.